package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/reorder-list/
 *
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 *
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * @author hanjuntao
 * @date 2025/8/7 0007
 */
public class L_143_重排链表 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        //node3.next = node4;
        //node4.next = node5;

        reorderList(node1);

        ListNode.print(node1);  //[1, 4, 2, 3]
    }

    /**
     * 从题意可知，是每遍历一个节点，将链表末尾的节点作为当前节点的next，同时删除掉末尾的节点
     *
     * 涉及链表的插入，删除及从后往前遍历
     *
     * 从后往前遍历有两种方式：
     * 1。 栈
     * 2. 反转链表
     *
     * 逻辑：
     * 1. 获取链表的长度
     * 2. 获取链表的中间节点
     * 3. 如果是偶数，则下一个链表的头节点为中间节点；如果是基数，则下一个链表的头节点为中间节点的下一个节点
     * 4. 反转下一个链表
     * 5. 遍历原链表，将当前节点的next指向下一个链表的头节点，直至遍历结束
     *
     * @param head
     */
    public static void reorderList(ListNode head) {
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        int mid = (length) / 2 + 1;

        curr = head;
        int count = 0;
        ListNode pre = null;
        ListNode nextHead = null;
        while (curr != null) {
            count++;
            if (count == mid) {
                // 如果长度为偶数，则midNode为中间节点
                // 如果长度为奇数，则midNode为中间节点的一个节点，中间节点不参与构造
                boolean isEven = length % 2 == 0;
                if (isEven) {
                    nextHead = curr;
                    pre.next = null;
                } else {
                    nextHead = curr.next;
                    curr.next = null;
                }
                break;
            }

            pre = curr;
            curr = curr.next;
        }

        nextHead  = reverse(nextHead);

        curr = head;
        ListNode curr2 = nextHead;

        // 将链表进行连接
        while (curr != null && curr2 != null) {
            ListNode next = curr.next;
            ListNode next2 = curr2.next;

            curr.next = curr2;
            curr2.next = next;

            curr = next;
            curr2 = next2;
        }
    }

    private static ListNode reverse(ListNode midNode) {
        if (midNode == null || midNode.next == null) {
            return midNode;
        }

        ListNode newHead = reverse(midNode.next);
        ListNode next = midNode.next;
        next.next = midNode;
        midNode.next = null;
        return newHead;
    }
}
